package dem1;

import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.Stack;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 33013
 * Date: 2023-04-14
 * Time: 12:30
 */
public class Test {

    ListNode head;

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public void add(int val){
        ListNode cur = head;
        ListNode node = new ListNode(val);
        if (head == null){
            head = node;
            return;
        }
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushA.length; i++){
            stack.push(pushA[i]);
            while(j < pushA.length && !stack.empty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0), pre;
        dummy.next = head;

        while(head != null && head.next != null) {
            if(head.val <= head.next.val) {
                head = head.next;
                continue;
            }
            pre = dummy;

            while (pre.next.val < head.next.val) pre = pre.next;

            ListNode curr = head.next;
            head.next = curr.next;
            curr.next = pre.next;
            pre.next = curr;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        int[] a = {2,1,0};
        int[] b = {1,2,0};
        //boolean x = new Test().IsPopOrder(a,b);
        Test test = new Test();//[-1,5,3,4,0]
        test.add(-1);
        test.add(5);
        test.add(3);
        test.add(4);
        test.add(0);
        test.insertionSortList(test.head);
        StringBuffer str = new StringBuffer();
        str.reverse();
    }
}

class Solution {

     public ListNode head;

    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public void add(int val){
        ListNode cur = head;
        ListNode node = new ListNode(val);
        if (head == null){
            head = node;
            return;
        }
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

    public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuffer str1 = new StringBuffer();
        StringBuffer str2 = new StringBuffer();
        while(l1 != null){
            str1.append(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            str2.append(l2.val);
            l2 = l2.next;
        }
        str1 = str1.reverse();
        str2 = str2.reverse();
        String str = bigNumSum(str1,str2);
        ListNode haed = new ListNode();
        ListNode cur = haed;
        for(int i = 0; i < str.length(); i++){
            ListNode node = new ListNode(str.charAt(i) - '0');
            cur.next = node;
            cur = node;
        }
        return haed.next;
    }
    private String bigNumSum(StringBuffer str1,StringBuffer str2){
        int min = 0;
        int max = 0;
        StringBuffer str3 = null;
        if(str1.length() > str2.length()){
            max = str1.length();
            min = str2.length();
            str3 = str1;
        }else{
            min = str1.length();
            max = str2.length();
            str3 = str2;
        }
        StringBuffer str = new StringBuffer(max + 1);
        int carry = 0;
        for(int i = 0; i < min; i++){
            carry += str1.charAt(i) + str2.charAt(i) - '0' - '0';
            str.append(carry % 10);
            carry /= 10;
        }
        for(int i = min; i < max; i++){
            carry += str3.charAt(i) - '0';
            str.append(carry % 10);
            carry /= 10;
        }
        if(carry != 0){
            str.append(carry);
        }
        str = str.reverse();
        return str.toString();
    }

    public static void main(String[] args) {//l1 = [7,2,4,3], l2 = [5,6,4]
        Solution solution1 = new Solution();
        solution1.add(7);
        solution1.add(2);
        solution1.add(4);
        solution1.add(3);
        Solution solution2 = new Solution();
        solution2.add(5);
        solution2.add(6);
        solution2.add(4);
        solution1.addTwoNumbers(solution1.head,solution2.head);
        Deque<Integer> deque = new <Integer>() ()
    }
}
